package cn.algorithm.sort;

/**
 * 计数排序
 *
 * @author dunlingiz
 * @date 2024/3/12
 * @since v
 */
public class CountSort {

    /**
     * 不保证顺序的情况下
     */
    public static int[] countSort(int[] array) {
        // 遍历数据，获取最大值、最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
            if (min > array[i]) {
                min = array[i];
            }
        }

        // 定义统计数组并遍历数组，将当前元素的值减去最小值，
        int dev = max - min;
        int[] countArray = new int[dev + 1];
        for (int k : array) {
            countArray[k - min]++;
        }

        // 遍历统计数组，
        int index = 0;
        int[] sortArray = new int[array.length];
        // 遍历统计数组，统计数组的元素索引下标 加上最小值就是原始数列的最小元素
        for (int i = 0; i < countArray.length; i++) {
            // 遍历统计数据当前的元素的统计个数
            for (int j = 0; j < countArray[i]; j++) {
                sortArray[index++] = i + min;
            }
        }
        return sortArray;
    }

    /**
     * 稳定情况，
     */
    public static int[] stableCountSort(int[] array) {
        // 遍历数据，获取最大值、最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
            if (min > array[i]) {
                min = array[i];
            }
        }

        // 定义统计数组,统计数组的长度为数组最大值减去最小值的偏差值 + 1
        int dev = max - min;
        int[] countArray = new int[dev + 1];
        // 遍历原数组，将当前元素减去最小值的偏差值作为统计数组的索引下标并进行自增
        // 对每个元素进行统计
        for (int k : array) {
            countArray[k - min]++;
        }

        //变形统计数据,遍历数组，将每个元素都加上之前元素之和，作为最终排序位置的序号
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] = countArray[i] + countArray[i - 1];
        }

        // 倒序遍历原数组=>保证相同元素的顺不变，稳定排序
        int[] sortArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            // 计算当前元素与最小值的偏差值
            int offset = array[i] - min;
            // 将偏差值作为统计数组索引下标，获取当前元素最终排序的序号，并减去1，就是排序数组的下标
            int index = countArray[offset] - 1;
            sortArray[index] = array[i];
            // 将统计数组当前元素对应的位置的序号自减，保证下次再出现相同的顺序
            countArray[offset]--;
        }
        return sortArray;
    }
}
